home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 9 / CDACTUAL9.iso / share / Dos / VARIOS / pascal / SWAG9605.DDD / 0037_Computing Perfect(prime) Numbers.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-05-31  |  3.4 KB  |  120 lines
  1. {
  2. >Samiel (samiel@fastlane.net) wrote:
  3. >: Here's my fast and elegant code... snarf it and add it to SWAG...
  4. >: 
  5. >: {****************************************************************
  6. >: Perfect Numbers...
  7. >: 
  8. >: A Perfect number is a number whose divisors not including the original
  9. >: number add up to the original number.  An example is 6, 6=3*2*1=3+2+1
  10. >: and 28, 28=14*7*4*2*1=14+7+4+2+1.  The definition of a Perfect number
  11. >: can also be defined as,
  12. >: 2^(p-1)*(2^p-1) where p is prime and 2^p-1 is a Mersenne prime...
  13. >: 
  14. >: A Mersenne prime is defined as,
  15. >: 2^p-1 where p is prime and 2^p-1 is prime, so 2^2-1=3 is a Mersenne
  16. >: prime where p is 2, and 2^3-1=5 is a Mersenne prime where p is 3.
  17. >: 
  18. >: Mersenne primes under 2^32 (32-bit) are:
  19. >:   [2] -> 3
  20. >:   [3] -> 7
  21. >:   [5] -> 31
  22. >:   [7] -> 127
  23. >: [13] -> 8191
  24. >: [17] -> 131071
  25. >: [19] -> 524287
  26. >: [31] -> 2147483647
  27. >: 
  28. >: (Values of p are in braces [])
  29. >: 
  30. >: The Perfect numbers under 2^32 are:
  31. >: Perfect numbers...
  32. >:   [2] 6
  33. >:   [3] 28
  34. >:   [5] 496
  35. >:   [7] 8128
  36. >: [13] 33550336
  37. >: 
  38. >: (Values of p are in braces [])
  39. >: 
  40. >: Here is my code...
  41. >:
  42. >: ****************************************************************}
  43.  
  44.  PROGRAM Perfect;
  45.  {Computes Perfect Numbers...}
  46.  
  47.  VAR
  48.    tmp,num:longint; {Long Integer signed 32-bit (31-bit on each side)}
  49.    j,k:byte;
  50.  
  51.  { Slow? Fast? way to find primes, dividing by odd numbers }
  52.  Function IsPrime(num:longint):boolean;
  53.  Var
  54.    tmp:boolean;
  55.    j:longint;
  56.  Begin
  57.    tmp:=true;
  58.    if num mod 2=0 then
  59.      tmp:=false;
  60.    for j:=3 to round(sqrt(num)) do
  61.      if odd(j) then
  62.        if num mod j=0 then
  63.          tmp:=false;
  64.    if num=2 then
  65.       tmp:=true;
  66.    IsPrime:=tmp;
  67.  End;
  68.  
  69.  BEGIN
  70.    tmp:=2; {2^1}
  71.    writeln('Perfect numbers...');
  72.    for j:=2 to 31 do
  73.      begin
  74.        tmp:=tmp*2; {Raise 2 to another power}
  75.        if IsPrime(j) then
  76.          begin
  77.            num:=tmp-1;
  78.            if IsPrime(num) then
  79.              begin
  80.                num:=num*(tmp div 2);
  81.                writeln(num:1,' is perfect'); {Ignore negatives}
  82.              end;
  83.          end;
  84.      end;
  85.  END.
  86.  
  87.  
  88. >: - Samiel
  89. >: samiel@fastlane.net
  90. >: http://www.fastlane.net/~samiel
  91. >: 
  92.  
  93. >Considering that 2^859433-1 is prime(and is the largest known prime), there
  94. >are obviously better methods.  Use the Lucas-Lehmer test.
  95.  
  96. >B(n+1) = B(n)^2 - 2 mod (2^p-1) where B(0)=4
  97.  
  98. >if B(n-1) = 0 then 2^p-1 is prime.  The division is a special case and is
  99. >done easily because of the all ONE's when 2^p-1 is written in binary.  All
  100. >that is necessary is a fast implementation of multiplication and this can
  101. >be done with FFT's.
  102.  
  103. >See http://www.utm.edu/research/primes/mersenne.shtml
  104.  
  105. >or for software
  106. >http://ourworld.compuserve.com/homepages/justforfun/prime.htm
  107.  
  108. Well, considering we are looking at numbers under 32 bits, your code
  109. would probably not get done as fast as mine, though in the long run,
  110. (say over 64 bits or so) it would.  All the FFT's and rather long
  111. multiplication would slow it down considerably.  Even if you could get
  112. a really fast implementation of FFT's and multiplications, we're
  113. talking about a net savings of about .625 seconds or so with numbers
  114. under 32 bits on a computer with a Math Processor... so mine's good
  115. enough... although a few of multiplications could be taken out...
  116.  
  117. - Samiel
  118. samiel@fastlane.net
  119. http://www.fastlane.net/~samiel
  120.